package org.basis.algorithm.list;

import org.basis.algorithm.list.common.ListNodeUtil;
import org.basis.algorithm.list.common.SingleNode;

import java.util.HashSet;

/**
 * 链表找环问题
 *
 * @author Mr_wenpan@163.com 2021/12/08 22:38
 */
public class ListFindLoop {

    public static void main(String[] args) {

//        testFindLoop();
//        testHasLoop();

    }

    private static void testFindLoop() {
        final int count = 1000;
        for (int j = 0; j < count; j++) {
            // 构建有环链表
            SingleNode<Integer> head = ListNodeUtil.generateIntegerSingleList(10, 10, true);
            // ListNodeUtil.printSingleList(head);
            SingleNode<Integer> p = head;
            for (int i = 0; i < 5; i++) {
                p = p.next;
            }
            SingleNode<Integer> q = p;
            q = q.next.next.next.next;
            q.next = p;
            //SingleNode<Integer> loopByPoint = findLoopByPoint(head);
            SingleNode<Integer> loopByPoint = findLoopByHashTable(head);
            if (loopByPoint != p) {
                System.out.println("入环节点寻找错误，算法有问题.");
            }
            //System.out.println("单链表环节点是：" + loopByPoint);
        }
    }

    private static void testHasLoop() {
        final int count = 10000;
        for (int i = 0; i < count; i++) {
            SingleNode<Integer> head = ListNodeUtil.generateIntegerSingleList(20, 30, false);
//            hasLoopByPoint(head);
            if (hasLoopByHashTable(head)) {
                System.out.println("找到环了，算法不正确。");
                break;
            }
        }

        // 测试链表找环，并返回入环节点
        for (int i = 0; i < count; i++) {
            SingleNode<Integer> singleNode = ListNodeUtil.generateIntegerSingleList(30, 30, false);
//            SingleNode<Integer> loopByPoint = findLoopByPoint(singleNode);
            SingleNode<Integer> loopByPoint = findLoopByHashTable(singleNode);
            if (loopByPoint != null) {
                System.out.println("单链表上找到环了，算法不正确。");
                break;
            }
        }
    }

    /**
     * 通过hash表判断链表是否有环
     */
    private static boolean hasLoopByHashTable(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return false;
        }
        HashSet<SingleNode<Integer>> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return true;
            } else {
                set.add(head);
            }
            head = head.next;
        }
        return false;
    }

    /**
     * 根据hash表找到入环节点
     */
    private static SingleNode<Integer> findLoopByHashTable(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return null;
        }
        HashSet<SingleNode<Integer>> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return head;
            } else {
                set.add(head);
            }
            head = head.next;
        }
        return null;
    }

    /**
     * 通过快慢指针判断链表是否有环
     */
    private static boolean hasLoopByPoint(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return false;
        }
        SingleNode<Integer> fast = head;
        SingleNode<Integer> slow = head;

        // 如果有环，满指针总会追上快指针
        while (fast != null && fast.next != null && slow != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return true;
            }
        }

        return false;
    }

    /**
     * 根据快慢指针来找环
     */
    private static SingleNode<Integer> findLoopByPoint(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return null;
        }

        SingleNode<Integer> fast = head;
        SingleNode<Integer> slow = head;
        while (fast != null && fast.next != null && slow != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }

        // 由于快指针走到头而造成的while退出，说明无环
        if (fast == null || fast.next == null) {
            return null;
        }

        // 有环的情况，快指针重头开始走
        fast = head;
        while (fast != null && slow != null) {
            if (fast == slow) {
                return fast;
            }
            fast = fast.next;
            slow = slow.next;
        }

        return null;
    }

}
